{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Palindrome Partitioning II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCut"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割回文串 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code>，请你将 <code>s</code> 分割成一些子串，使每个子串都是回文。</p>\n",
    "\n",
    "<p>返回符合要求的 <strong>最少分割次数</strong> 。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aab\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>只需一次分割就可将 <em>s </em>分割成 [\"aa\",\"b\"] 这样两个回文子串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"a\"\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ab\"\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length <= 2000</code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [palindrome-partitioning-ii](https://leetcode.cn/problems/palindrome-partitioning-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [palindrome-partitioning-ii](https://leetcode.cn/problems/palindrome-partitioning-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aab\"', '\"a\"', '\"ab\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        #当s本身是个回文串的时候，我们自然不做出任何判断，当s不是的时候，我们开始找“刀子”去分割字符串，而数组dp[i]其实存储的就是在前i个长度的字符串被分割的最小次数。\n",
    "        #程序里面，i是当前被回文的子字符串的总长，j是那把“刀子”，我们不断的切割字符串\n",
    "\n",
    "        #动态规划的思想\n",
    "        #状态定义：dp[i] 是以 i 结尾的分割成回文串的最少次数\n",
    "        #状态转移方程：dp[i]=min(dp[i],dp[j]+1);如果 isPalindrome(s[j+1..i])\n",
    "\n",
    "        #状态转移方程分析，dp[j]是以j结尾的分割最小次数，那么必须保证s[j+1:i+1]是回文串，\n",
    "        #遍历所有的j=[0,i-1]，那么dp[i]就是所有的 s[j + 1..i] 是回文字符串的情况下， dp[j]的最小值 + 1。\n",
    "\n",
    "        n=len(s)\n",
    "        if s==s[::-1]: #两个剪枝\n",
    "            return 0  \n",
    "        for i in range(1, n):\n",
    "            if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:\n",
    "                return 1\n",
    "                \n",
    "        dp=[n]*n #初始可以看作一个长度为n的字符串，若把它分为n个单独的字符，那肯定是满足要求，也即是最大的分割次数\n",
    "        for i in range(n):\n",
    "            if self.ishuiwen(s[0:i+1]): #剪枝，若前i个字符本身就是回文串，不需要再额外分割，更新i位置的dp为0\n",
    "                dp[i]=0\n",
    "                continue\n",
    "            for j in range(i):\n",
    "                if self.ishuiwen(s[j+1:i+1]):\n",
    "                    dp[i]=min(dp[i],dp[j]+1)\n",
    "        return dp[n-1]\n",
    "\n",
    "    def ishuiwen(self,s):\n",
    "        return s==s[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            if s[0:i] == s[0: i][::-1]:\n",
    "                return 0\n",
    "\n",
    "            res = inf\n",
    "            for j in range(0, i):\n",
    "                if s[j: i] == s[j: i][::-1]:\n",
    "                    res = min(res, dfs(j))\n",
    "            return res + 1\n",
    "\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            if s[0:i + 1] == s[0: i + 1][::-1]:\n",
    "                return 0\n",
    "\n",
    "            res = inf\n",
    "            for j in range(0, i + 1):\n",
    "                if s[j: i + 1] == s[j: i + 1][::-1]:\n",
    "                    res = min(res, dfs(j - 1))\n",
    "            return res + 1\n",
    "\n",
    "        return dfs(n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = n - i\n",
    "            for j in range(i, n):\n",
    "                sub = s[i:j+1]\n",
    "                if sub == sub[::-1]:\n",
    "                    res = min(res, f(j+1) + 1)\n",
    "            return res\n",
    "        return f(0) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        def is_huiwen(s):\n",
    "            return s[::-1] == s\n",
    "\n",
    "        res_dic = {}\n",
    "        def dfs(s):\n",
    "            if s == '':\n",
    "                return 0\n",
    "            if s in res_dic:\n",
    "                return res_dic[s]\n",
    "            min_res = float('inf')\n",
    "            for i in range(len(s)):\n",
    "                if is_huiwen(s[:i+1]):\n",
    "                    if i < len(s) - 1:\n",
    "                        min_res = min(min_res, 1 + dfs(s[i+1:]))\n",
    "                    else:\n",
    "                        min_res = 0\n",
    "            res_dic[s] = min_res\n",
    "            return min_res\n",
    "\n",
    "        return dfs(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @functools.lru_cache(None)\n",
    "    def minCut(self, s: str) -> int:\n",
    "        if s == s[::-1]:\n",
    "            return 0\n",
    "        ans = float(\"inf\")\n",
    "        for i in range(1, len(s) + 1):  #寻找切分点\n",
    "            if s[:i] == s[:i][::-1]:\n",
    "                ans = min(self.minCut(s[i:]) + 1, ans)  #切一刀\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    @functools.lru_cache(None)\n",
    "    def minCut(self, s: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(s):\n",
    "            if s == s[::-1]:\n",
    "                return 0\n",
    "            ans = float(\"inf\")\n",
    "            for i in range(1, len(s) + 1):\n",
    "                if s[:i] == s[:i][::-1]:\n",
    "                    ans = min(dfs(s[i:]) + 1, ans)\n",
    "            return ans\n",
    "        return dfs(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    @functools.lru_cache(None)\n",
    "    def minCut(self, s: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(s):\n",
    "            if s == s[::-1]:\n",
    "                return 0\n",
    "            ans = float(\"inf\")\n",
    "            for i in range(1, len(s) + 1):\n",
    "                if s[:i] == s[:i][::-1]:\n",
    "                    ans = min(dfs(s[i:]) + 1, ans)\n",
    "            return ans\n",
    "        return dfs(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def minCut(self, s: str) -> int:\n",
    "        if s==s[::-1]:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for i in range(1,len(s)+1):\n",
    "            if s[:i] ==s[:i][::-1]:\n",
    "                ans = min(self.minCut(s[i:])+1,ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        def __isRcs__(l, r):\n",
    "            for i in range((l + r + 1) // 2 - l):\n",
    "                if s[l + i] != s[r - i]:\n",
    "                    return False\n",
    "            return True\n",
    "        n = len(s)\n",
    "        dp = dict()\n",
    "        query = collections.deque()\n",
    "        query.append((0, 0))\n",
    "        while (len(query) > 0):\n",
    "            cidx, cn = query.popleft()\n",
    "            if cidx in dp:\n",
    "                continue           \n",
    "            dp[cidx] = cn\n",
    "            if cidx == n:\n",
    "                break\n",
    "            \n",
    "            for r in range(n - 1, cidx - 1, -1):\n",
    "            # for r in range(cidx, n):\n",
    "                if __isRcs__(cidx, r):\n",
    "                    query.append((r + 1, cn + 1))\n",
    "            # if not should_break:\n",
    "            #     query.append((cidx, True, cslices))\n",
    "            #     for nidx in cslices:\n",
    "            #         query.append((nidx, False, None))\n",
    "        \n",
    "        return dp[n] - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        N = len(s)\n",
    "        dp2 = [[1] for i in range(N)]\n",
    "        for i in range(1,N):\n",
    "            if s[i]==s[i-1]:\n",
    "                dp2[i].append(2)\n",
    "        for k in range(2,N):\n",
    "            for j in range(k,N):\n",
    "                if s[j-k]==s[j]:\n",
    "                    t = len(dp2[j-1])-1\n",
    "                    while t>=0 and dp2[j-1][t]>=k-1:\n",
    "                        if dp2[j-1][t]==k-1:\n",
    "                            dp2[j].append(k+1)\n",
    "                        t-=1\n",
    "            \n",
    "        dp1 = [N]*N\n",
    "        # print(dp2)\n",
    "        for i in range(N):\n",
    "            for k in dp2[i]:\n",
    "                if k == i+1:\n",
    "                    dp1[i] = 0\n",
    "                    break\n",
    "                dp1[i] = min(dp1[i],dp1[i-k]+1)\n",
    "        # print(dp1)\n",
    "        return dp1[N-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * (n-i) for i in range(n)] # dp[i][j] 代表以s[i]开头长度为(j+1)的字符串是否为回文子串\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-i):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = True\n",
    "                elif j == 1:\n",
    "                    if s[i] == s[i+1]:\n",
    "                        dp[i][j] = True\n",
    "                else:\n",
    "                    if dp[i+1][j-2] and s[i] == s[i+j]:\n",
    "                        dp[i][j] = True\n",
    "        \n",
    "        dp_split = [float(\"inf\")]*(n+1) # dp[i]代表0:i的最小分割次数\n",
    "        dp_split[0] = -1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i):\n",
    "                if dp[j][i-j-1]:\n",
    "                    dp_split[i] = min(dp_split[i], dp_split[j] + 1)\n",
    "        return dp_split[-1]\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        flags = [[True for j in range(i+2)] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                flags[i][j] = flags[i-1][j+1] and s[i] == s[j]\n",
    "        dp = [i for i in range(n)]\n",
    "        for i in range(1, n):\n",
    "            if flags[i][0]:\n",
    "                dp[i] = 0\n",
    "            else:\n",
    "                for j in range(1, i + 1):\n",
    "                    if flags[i][j]:\n",
    "                        dp[i] = min(dp[i], dp[j-1] + 1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "\n",
    "        dp = [[None] * (len(s) + 1 - i) for i in range(len(s))]\n",
    "\n",
    "        for i in range(len(dp)):\n",
    "            dp[i][0] = dp[i][1] = True\n",
    "\n",
    "        for j in range(2, len(dp[0])):\n",
    "\n",
    "            for i in range(len(dp) - j + 1):\n",
    "\n",
    "                if dp[i + 1][j - 2] and s[i] == s[i + j - 1]:\n",
    "                    dp[i][j] = True\n",
    "                else:\n",
    "                    dp[i][j] = False\n",
    "\n",
    "        dp_min=[0]*(len(s))\n",
    "        for i in range(1,len(dp_min)):\n",
    "            if dp[0][i+1]:\n",
    "                dp_min[i]=0\n",
    "                continue\n",
    "            cur_ls=[]\n",
    "            for j in range(i):\n",
    "                if dp[j+1][i-(j)]:\n",
    "                    cur_ls.append(dp_min[j]+1)\n",
    "            dp_min[i]=min(cur_ls)\n",
    "        # print(dp_min)\n",
    "        return dp_min[-1]\n",
    "\n",
    "        # min_cz=len(s)-1\n",
    "        memo = {}\n",
    "\n",
    "        def compute_min(start, l):\n",
    "\n",
    "            if dp[start][l]:\n",
    "                return 0\n",
    "            if (start, l) in memo:\n",
    "                return memo[(start, l)]\n",
    "            min_cur = l - 1\n",
    "            for i in range(1, l):\n",
    "                min_cur = min(min_cur, compute_min(start, i) + compute_min(start + i, l - i) + 1)\n",
    "            memo[(start, l)] = min_cur\n",
    "            return min_cur\n",
    "        dp_min=[[0]*(len(s)-i+1)for i in range(len(s))]\n",
    "\n",
    "        for j in range(2, len(dp_min[0])):\n",
    "\n",
    "            for i in range(len(dp_min) - j +1):\n",
    "\n",
    "                if dp[i][j]:\n",
    "\n",
    "                    continue\n",
    "                l=j\n",
    "                min_cur=l-1\n",
    "                for index in range(1, l):\n",
    "                    # print(i,j)\n",
    "                    min_cur = min(min_cur, dp_min[i][index] + dp_min[i+index] [l - index] + 1)\n",
    "                dp_min[i][j]=min_cur\n",
    "        # print(dp_min)\n",
    "        # for row in dp_min:\n",
    "        #     print(row)\n",
    "        return dp_min[0][-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        res = compute_min(0, len(s))\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        L = len(s)\n",
    "        if L == 0:\n",
    "            return [[]]\n",
    "        sym = [[True]*L,[True]*L]\n",
    "        for l in range(2,L+1):\n",
    "            sym.append([])\n",
    "            for i in range(L-l+1):\n",
    "                sym[-1].append(sym[l-2][i+1] and s[i]==s[i+l-1])\n",
    "        cut = [0]\n",
    "        for i in range(1,L):\n",
    "            if sym[i+1][0]:\n",
    "                cut.append(0)\n",
    "            else:\n",
    "                m = i\n",
    "                for j in range(i):\n",
    "                    if sym[i-j][j+1]:\n",
    "                        m = min(m,cut[j]+1)\n",
    "                cut.append(m)\n",
    "        #print(sym,cut)\n",
    "        return cut[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        N = len(s)\n",
    "        array = [[False] * N for i in range(N)]\n",
    "        for i in range(N):\n",
    "            i1, i2 = i, i\n",
    "            while(i1 >= 0 and i2 < N and s[i1] == s[i2]):\n",
    "                array[i1][i2] = True\n",
    "                i1 -= 1\n",
    "                i2 += 1\n",
    "            \n",
    "            i1, i2 = i - 1, i\n",
    "            while(i1 >= 0 and i2 < N and s[i1] == s[i2]):\n",
    "                array[i1][i2] = True\n",
    "                i1 -= 1\n",
    "                i2 += 1\n",
    "        \n",
    "        visited_dict = {-1: 0}\n",
    "        def dfs(n):\n",
    "            if n in visited_dict:\n",
    "                return visited_dict[n]\n",
    "\n",
    "            cur_min = inf\n",
    "            for i in range(n + 1):\n",
    "                if array[i][n]:\n",
    "                    cur_min = min(cur_min, dfs(i - 1))\n",
    "\n",
    "            visited_dict[n] = cur_min + 1\n",
    "            return visited_dict[n]\n",
    "        \n",
    "        return dfs(N - 1) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        starts=[[i] for i in range(n)] #starting points\n",
    "        cuts=[0]+(n-1)*[float('inf')]\n",
    "        for i in range(1,n):\n",
    "            cuts[i]=min(cuts[i], cuts[i-1]+1)\n",
    "            if s[i]==s[i-1]: \n",
    "                starts[i].append(i-1)\n",
    "                if i==1: cuts[i]=0\n",
    "                else: cuts[i]=min(cuts[i], cuts[i-2]+1)\n",
    "\n",
    "            for start in starts[i-1]:\n",
    "                if start==0: cuts[i]=min(cuts[i], 1)\n",
    "                elif s[i]==s[start-1]: \n",
    "                    starts[i].append(start-1)\n",
    "                    if start==1: \n",
    "                        cuts[i]=0\n",
    "    \n",
    "                    else:\n",
    "                        cuts[i]=min(cuts[i], cuts[start-2]+1)\n",
    "        \n",
    "        return cuts[n-1]\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ManacherPlindrome:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def manacher(s):\n",
    "        # 马拉车算法\n",
    "        n = len(s)\n",
    "        arm = [0] * n\n",
    "        left, right = 0, -1\n",
    "        for i in range(0, n):\n",
    "            a, b = arm[left + right - i], right - i + 1\n",
    "            a = a if a < b else b\n",
    "            k = 1 if i > right else a\n",
    "            \n",
    "            # 持续增加回文串的长度\n",
    "            while 0 <= i - k and i + k < n and s[i - k] == s[i + k]:\n",
    "                k += 1\n",
    "            arm[i] = k\n",
    "\n",
    "            # 更新右侧最远的回文串边界\n",
    "            k -= 1\n",
    "            if i + k > right:\n",
    "                left = i - k\n",
    "                right = i + k\n",
    "        # 返回每个位置往右的臂长其中 s[i-arm[i]+1: i+arm[i]] 为回文子串范围\n",
    "        # 即以i为中心的最长回文子串长度\n",
    "        return arm\n",
    "\n",
    "    def palindrome(self, s: str) -> (list, list):\n",
    "        # 获取区间的回文串信息\n",
    "        n = len(s)\n",
    "        # 保证所有的回文串为奇数长度，且中心为 # 的为原偶数回文子串，中心为 字母 的为原奇数回文子串\n",
    "        t = \"#\" + \"#\".join(list(s)) + \"#\"\n",
    "        dp = self.manacher(t)\n",
    "        m = len(t)\n",
    "        # 以当前索引作为边界结尾的回文子串起始位置索引\n",
    "        end = [[] for _ in range(n)]\n",
    "\n",
    "        for j in range(m):\n",
    "            left = j - dp[j] + 1\n",
    "            right = j + dp[j] - 1\n",
    "            while left <= right:\n",
    "                if t[left] != \"#\":\n",
    "                    end[right//2].append(left//2)\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        return end\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        end = ManacherPlindrome().palindrome(s)\n",
    "\n",
    "        dp2 = [n] * (n + 1)\n",
    "        dp2[0] = 0\n",
    "        for i in range(n):\n",
    "            for j in end[i]:\n",
    "                if dp2[j] + 1 < dp2[i + 1]:\n",
    "                    dp2[i + 1] = dp2[j] + 1\n",
    "        return dp2[-1] - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        length=len(s)\n",
    "        hdict=defaultdict(list)\n",
    "        for i in range(length):\n",
    "            j,k=0,0\n",
    "            while i-j>=0 and i+j<length and s[i-j]==s[i+j]:\n",
    "                hdict[i+j].append(i-j)\n",
    "                j+=1\n",
    "            if i<length-1 and s[i]==s[i+1]:\n",
    "                while i-k>=0 and i+1+k<length and s[i-k]==s[i+1+k]:\n",
    "                    hdict[i+1+k].append(i-k)\n",
    "                    k+=1   \n",
    "        for v in hdict.values():\n",
    "            v.sort()\n",
    "        dp=[float(\"inf\")]*length\n",
    "        dp[0]=1\n",
    "        for i in range(1,length):\n",
    "            if hdict[i][0]==0:\n",
    "                dp[i]=1\n",
    "            else:\n",
    "                dp[i]=min(dp[x-1] for x in hdict[i] if x>0)+1\n",
    "        pass\n",
    "        return dp[-1]-1\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        # s=\"cbbbcc\"\n",
    "        n=len(s)\n",
    "        res=n-1\n",
    "        dic={}\n",
    "        for i in range(0,n):\n",
    "            dic[i]=[]\n",
    "        arr=[[i,i] for i in range(0,n)]\n",
    "        for i in range(0,n-1):\n",
    "            if s[i]==s[i+1]:\n",
    "                arr.append([i,i+1])\n",
    "        while len(arr)>0:\n",
    "            tmp=[]\n",
    "            for i in arr:\n",
    "                st=i[0]\n",
    "                ed=i[1]\n",
    "                dic[st].append(ed)\n",
    "                if st>0 and ed<n-1 and s[st-1]==s[ed+1]:\n",
    "                    tmp.append([st-1,ed+1])\n",
    "            arr=tmp\n",
    "        # print(dic)\n",
    "        lst=[n-1 for i in range(0,n)]\n",
    "        lst[0]=0\n",
    "        for i in range(0,n):\n",
    "            tmp=dic[i]\n",
    "            for j in tmp:\n",
    "                if j==n-1:\n",
    "                    res=min(res,lst[i])\n",
    "                else:\n",
    "                    lst[j+1]=min(lst[i]+1,lst[j+1])\n",
    "        # print(lst)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        res=n-1\n",
    "        dic={}\n",
    "        for i in range(0,n):\n",
    "            dic[i]=[]\n",
    "        arr=[[i,i] for i in range(0,n)]\n",
    "        for i in range(0,n-1):\n",
    "            if s[i]==s[i+1]:\n",
    "                arr.append([i,i+1])\n",
    "        while len(arr)>0:\n",
    "            tmp=[]\n",
    "            for i in arr:\n",
    "                st=i[0]\n",
    "                ed=i[1]\n",
    "                dic[st].append(ed)\n",
    "                if st>0 and ed<n-1 and s[st-1]==s[ed+1]:\n",
    "                    tmp.append([st-1,ed+1])\n",
    "            arr=tmp\n",
    "        lst=[n-1 for i in range(0,n)]\n",
    "        lst[0]=0\n",
    "        for i in range(0,n):\n",
    "            tmp=dic[i]\n",
    "            for j in tmp:\n",
    "                if j==n-1:\n",
    "                    res=min(res,lst[i])\n",
    "                else:\n",
    "                    lst[j+1]=min(lst[i]+1,lst[j+1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        length=len(s)\n",
    "        index=[[i] for i in range(length)]\n",
    "        for i in range(length-2,-1,-1):\n",
    "            if s[i+1]==s[i]: index[i].append(i+1)\n",
    "            for j in index[i+1]:\n",
    "                if j+1<length and s[j+1]==s[i]:index[i].append(j+1)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i>=length: return 0\n",
    "            ret=length-i\n",
    "            for j in index[i]:\n",
    "                ret=min(ret,dfs(j+1)+1)\n",
    "            return ret\n",
    "        return min([dfs(i+1) for i in index[0]])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        hashmap={0:[0]}\n",
    "        for i in range(1,len(s)):\n",
    "            key=[i]\n",
    "            if s[i]==s[i-1]:\n",
    "                key.append(i-1)\n",
    "            for j in  hashmap[i-1]:\n",
    "                if j!=0:\n",
    "                    if s[j-1]==s[i]:\n",
    "                        key.append(j-1)\n",
    "                 \n",
    "            hashmap[i]=key\n",
    "        print(hashmap)\n",
    "        dp=[i for i in range(len(s)+1)]\n",
    "        for i in range(1,len(s)):\n",
    "            for j in hashmap[i]:\n",
    "                dp[i+1]=min(dp[i+1],dp[j]+1)\n",
    "        print(dp)\n",
    "        return dp[-1]-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        if len(s) == 1:\n",
    "            return 0\n",
    "        arr = [[0 for i in s] for m in s]\n",
    "        maxValue = 0\n",
    "        maxGap = [0, 0]\n",
    "        # print(s)\n",
    "        for gap in range(len(arr)):\n",
    "            for _ in range(len(arr)):\n",
    "                if _ + gap >= len(arr):\n",
    "                    continue\n",
    "                if gap == 0:\n",
    "                    arr[_][_ + gap] = 1\n",
    "                    continue\n",
    "                elif gap == 1:\n",
    "                    if s[_] == s[_+gap]:\n",
    "                        arr[_][_ + gap] = arr[_ + 1][_ + gap - 1] + 2\n",
    "                        if arr[_][_ + gap] > maxValue:\n",
    "                            maxValue = arr[_][_ + gap]\n",
    "                            maxGap = [_, _ + gap]\n",
    "                else:\n",
    "\n",
    "                    if s[_] == s[_ + gap] and arr[_ + 1][_ + gap - 1] > 0:\n",
    "                        arr[_][_ + gap] = arr[_ + 1][_ + gap - 1] + 2\n",
    "                        if arr[_][_ + gap] > maxValue:\n",
    "                            maxValue = arr[_][_ + gap]\n",
    "                            maxGap = [_, _ + gap]\n",
    "\n",
    "        f = [float(\"inf\")] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if arr[0][i] > 0:\n",
    "                f[i] = 0\n",
    "            else:\n",
    "                for j in range(i):\n",
    "                    if arr[j + 1][i] > 0:\n",
    "                        f[i] = min(f[i], f[j] + 1)\n",
    "\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        ### solution\n",
    "        # DP + Backtrack w Memo\n",
    "        # DP + DP\n",
    "\n",
    "        ## DP + DP O(n2) O(n2)\n",
    "        # 1. DP dpValid[i][j] is Palindrome\n",
    "        # 2. DP dpCut[i] the min cut for s[0:i+1]\n",
    "        n = len(s)\n",
    "        dpValid = [[False]*n for _ in range(n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i,n):\n",
    "                if s[i]==s[j] and (j-i<2 or dpValid[i+1][j-1]):\n",
    "                    dpValid[i][j] = True\n",
    "        dpCut = [n]*n\n",
    "        for i in range(n):\n",
    "            if dpValid[0][i]: dpCut[i] = 0\n",
    "            else:\n",
    "                for j in range(i, -1, -1): # j from 1 to i or 0 to i\n",
    "                    if dpValid[j][i]:\n",
    "                        dpCut[i] = min(dpCut[i], dpCut[j-1]+1)\n",
    "        return dpCut[-1]\n",
    "\n",
    "        ## DP + Backtrack-Memorization\n",
    "        # dp[i][j] -> s[i:j+1] is Palindrome or not\n",
    "        # memo[start] - the min number of palindromes in s[start:n]\n",
    "        # min cut is mem[start]-1\n",
    "        def backtrack(start):\n",
    "            if start==n:\n",
    "                return 0\n",
    "            if memo[start]==-1:\n",
    "                count = n\n",
    "                for i in range(start,n):\n",
    "                    if dp[start][i]:\n",
    "                        count = min(count, 1+backtrack(i+1))\n",
    "                memo[start] = count\n",
    "            return memo[start]\n",
    "            \n",
    "        n = len(s)\n",
    "        dp = [[False]*n for _ in range(n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i,n):\n",
    "                if s[i]==s[j] and (j-i<2 or dp[i+1][j-1]):\n",
    "                    dp[i][j] = True\n",
    "        memo = [-1]*n\n",
    "        backtrack(0)\n",
    "        return memo[0]-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    # @functools.lru_cache(None)\n",
    "    def minCut(self, s: str) -> int:\n",
    "    #     if s == s[::-1]:\n",
    "    #         return 0\n",
    "\n",
    "    #     ans = float(\"inf\")\n",
    "    #     for i in range(1,len(s)+1):\n",
    "    #         if s[:i] == s[:i][::-1]:\n",
    "    #             ans = min(self.minCut(s[i:])+1,ans)\n",
    "\n",
    "    #     return ans\n",
    "        # method2:动态规划\n",
    "        # if s == s[::-1]:\n",
    "        #     return 0\n",
    "        # for i in range(1, len(s) + 1):\n",
    "        #     if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:\n",
    "        #         return 1\n",
    "        \n",
    "        # min_cut = list(range(len(s)))\n",
    "        # n = len(s)\n",
    "        # dp =[[False] * n for i in range(n)]\n",
    "        # for j in range(n):\n",
    "        #     for i in range(j+1):\n",
    "        #         if s[i] == s[j] and (j-i < 2 or dp[i+1][j-1]):\n",
    "        #             dp[i][j] = True\n",
    "        #             if i == 0:\n",
    "        #                 min_cut[j] = 0\n",
    "        #             else:\n",
    "        #                 min_cut[j] = min(min_cut[j],min_cut[i-1]+1)\n",
    "        # return min_cut[-1]\n",
    "\n",
    "        n = len(s)\n",
    "        if s == s[::-1]:\n",
    "            return 0\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:\n",
    "                return 1\n",
    "\n",
    "        dp = [[False]*n for _ in range(n)]\n",
    "        min_cut = list(range(n))\n",
    "\n",
    "        for j in range(n):\n",
    "            for i in range(j+1):\n",
    "                if s[i] == s[j] and (j-i < 2 or dp[i+1][j-1]):\n",
    "                    dp[i][j] = True\n",
    "                    if i == 0:\n",
    "                        min_cut[j] = 0\n",
    "                    else:\n",
    "                        min_cut[j] = min(min_cut[j],min_cut[i-1]+1)\n",
    "\n",
    "        return min_cut[-1]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    # @functools.lru_cache(None)\n",
    "    def minCut(self, s: str) -> int:\n",
    "    #     if s == s[::-1]:\n",
    "    #         return 0\n",
    "\n",
    "    #     ans = float(\"inf\")\n",
    "    #     for i in range(1,len(s)+1):\n",
    "    #         if s[:i] == s[:i][::-1]:\n",
    "    #             ans = min(self.minCut(s[i:])+1,ans)\n",
    "\n",
    "    #     return ans\n",
    "        # method2:动态规划\n",
    "        # if s == s[::-1]:\n",
    "        #     return 0\n",
    "        # for i in range(1, len(s) + 1):\n",
    "        #     if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:\n",
    "        #         return 1\n",
    "        \n",
    "        # min_cut = list(range(len(s)))\n",
    "        # n = len(s)\n",
    "        # dp =[[False] * n for i in range(n)]\n",
    "        # for j in range(n):\n",
    "        #     for i in range(j+1):\n",
    "        #         if s[i] == s[j] and (j-i < 2 or dp[i+1][j-1]):\n",
    "        #             dp[i][j] = True\n",
    "        #             if i == 0:\n",
    "        #                 min_cut[j] = 0\n",
    "        #             else:\n",
    "        #                 min_cut[j] = min(min_cut[j],min_cut[i-1]+1)\n",
    "        # return min_cut[-1]\n",
    "\n",
    "        n = len(s)\n",
    "        if s == s[::-1]:\n",
    "            return 0\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:\n",
    "                return 1\n",
    "\n",
    "        min_cut = list(range(n))\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            for i in range(j+1):\n",
    "                if s[i] == s[j] and (j-i<2 or dp[i+1][j-1]):\n",
    "                    dp[i][j] = True\n",
    "                    if i == 0:\n",
    "                        min_cut[j] = 0\n",
    "                    else:\n",
    "                        min_cut[j] = min(min_cut[j],min_cut[i-1]+1)\n",
    "\n",
    "\n",
    "        return min_cut[-1]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        # import functools\n",
    "        n=len(s)\n",
    "        # dp\n",
    "        # dp[i] define as partition when i==rightmost\n",
    "        # loop last subarray from i <--to left, \n",
    "        # when lastsub is palindrome, refer to dp[i-len(sub)]+1\n",
    "        dp=[float('inf') for i in range(n)]\n",
    "        dp[0]=0#one letter is palindrome, no need cut\n",
    "        # @functools.lru_cache(maxsize=None)\n",
    "        # def is_palindrome(left,right):#check subarray of s\n",
    "        #     if left>=right:return True\n",
    "        #     if s[left]!=s[right]:return False\n",
    "        #     return is_palindrome(left+1,right-1)\n",
    "\n",
    "        # update: try pre-calculate is_palindrome\n",
    "        is_palindrome=[[None for left in range(n)]for right in range(n)]\n",
    "        for right_left in range(n):#right-left\n",
    "            for left in range(0,n-right_left):\n",
    "                right=left+right_left\n",
    "                if left==right:is_palindrome[left][right]=True;continue\n",
    "                if s[left]!=s[right]:is_palindrome[left][right]=False\n",
    "                elif right-left+1==2:#if len==2\n",
    "                    is_palindrome[left][right]=True\n",
    "                else:#refer to left+1, right-1\n",
    "                    is_palindrome[left][right]=is_palindrome[left+1][right-1]\n",
    "                \n",
    "        for i in range(1,n):\n",
    "            if is_palindrome[0][i]:#if all is palindrome\n",
    "                dp[i]=0;continue\n",
    "            for len_subarray in range(1,i+1):#check each palindrome sub\n",
    "                # subarray=i-len_subarray,i\n",
    "                if is_palindrome[i-len_subarray+1][i]:\n",
    "                    dp[i]=min(dp[i],dp[i-len_subarray]+1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[True] * n for _ in range(n)]\n",
    "        # dp[i][j] denotes the where the subarray s[i: j+1] is Palindrome\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]\n",
    "        \n",
    "        p_dp = [float('inf')] * n \n",
    "        # p_dp[i] denotes the min partition of palindrome substring for s[:i+1]\n",
    "\n",
    "        for i in range(n):\n",
    "            if dp[0][i]:\n",
    "                p_dp[i] = 0\n",
    "\n",
    "            for j in range(i):\n",
    "                if dp[j+1][i]:\n",
    "                    p_dp[i] = min(p_dp[i], p_dp[j] + 1)\n",
    "\n",
    "        return p_dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[True] * n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                f[i][j] = (s[i] == s[j]) and f[i+1][j-1]\n",
    "        \n",
    "        dp = [inf] * n\n",
    "        for i in range(n):\n",
    "            if f[0][i]: dp[i] = 0\n",
    "            else:\n",
    "                for j in range(i):\n",
    "                    if f[j+1][i]:\n",
    "                        dp[i] = min(dp[i], dp[j] + 1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, dp: List[List[bool]], i: int, j: int, mark: List[int]) -> int:\n",
    "        if i >= len(dp):\n",
    "           return 0\n",
    "        if mark[i] > -1:\n",
    "            return mark[i]\n",
    "        ans = len(dp) - j\n",
    "        for k in range(len(dp) - 1, j - 1, -1):\n",
    "            if dp[i][k]:\n",
    "                t = 1 + self.dfs(dp, k + 1, k + 1, mark)\n",
    "                # if t <= ans:\n",
    "                #     ans = t \n",
    "                # else:\n",
    "                #     mark[i][j] = ans\n",
    "                #     return ans\n",
    "                ans = min(ans, t)\n",
    "        mark[i] = ans\n",
    "        return ans\n",
    "\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[True] * n for _ in range(n)]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]\n",
    "        # print(dp)\n",
    "        mark = [-1] * n\n",
    "        return 0 if dp[0][-1] else self.dfs(dp, 0, 0, mark) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        g = [[i] for i in range(n)]\n",
    "        for i in range(n-1):\n",
    "            if s[i] == s[i+1]:\n",
    "                g[i].append(i+1)\n",
    "        for long in range(2, n):\n",
    "            for start in range(n-long):\n",
    "                if s[start] == s[start+long] and start+long-1 in g[start+1][-2:]:\n",
    "                    g[start].append(start+long)\n",
    "        # print(g)\n",
    "        vis = [0]*n\n",
    "        que = [(0, -1)]\n",
    "        while 1:\n",
    "            p, ans = que.pop(0)\n",
    "            if p == n:\n",
    "                return ans\n",
    "            if vis[p]:\n",
    "                continue\n",
    "            vis[p] = 1\n",
    "            for nxt in g[p][::-1]:\n",
    "                que.append((nxt+1, ans+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dp = []\n",
    "    dp1 = []\n",
    "\n",
    "    def f(self, begin, end):\n",
    "        if begin >= end or self.dp[begin][end]:\n",
    "            return 0\n",
    "        if self.dp1[begin][end] != None:\n",
    "            return self.dp1[begin][end]\n",
    "        ans = end - begin - 1\n",
    "        for i in range(begin+1, end):\n",
    "            if self.dp[begin][i]:\n",
    "                ans = min(ans, 1 + self.f(i, end))\n",
    "        self.dp1[begin][end] = ans\n",
    "        return ans\n",
    "\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        self.dp = [[False for i in range(n+1)] for j in range(n+1)]\n",
    "        for i in range(n):\n",
    "            self.dp[i][i] = self.dp[i][i+1] = True\n",
    "        for l in range(2, n+1):\n",
    "            for i in range(n-l+1):\n",
    "                self.dp[i][i+l] = s[i] == s[i+l-1] and self.dp[i+1][i+l-1]\n",
    "        self.dp1 = [[None for j in range(n+1)] for i in range(n+1)]\n",
    "        return self.f(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[False]*n for _ in range(n)]\n",
    "        edges = [[i-1]for i in range(n)] \n",
    "        for i in range(n):\n",
    "            dp[i][i] = True \n",
    "        for i in range(n-1):\n",
    "            if s[i]==s[i+1]:\n",
    "                dp[i][i+1] = True \n",
    "                edges[i+1].append(i-1)\n",
    "        for l in range(2,n):\n",
    "            for i in range(n-l):\n",
    "                if s[i]==s[i+l] and dp[i+1][i+l-1]:\n",
    "                    dp[i][i+l] = True\n",
    "                    edges[i+l].append(i-1) \n",
    "\n",
    "        # print(edges)\n",
    "        dp2 = [i for i in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for ip in edges[i]:\n",
    "                dp2[i+1] = min(dp2[ip+1]+1,dp2[i+1])\n",
    "        return dp2[n]-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 先储存每个回文子串的首尾dict = {end:[beginIdxs]}\n",
    "# dp[i]表示前i个字符能组成的最少回文段数\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp1 = [[False] * n for _ in range(n)]\n",
    "        hashmap = {}\n",
    "        for i in range(n):\n",
    "            dp1[i][i] = True\n",
    "            hashmap[i] = [i]\n",
    "        for i in range(n-1):\n",
    "            if s[i] == s[i+1]:\n",
    "                dp1[i][i+1] = True \n",
    "                hashmap[i+1].append(i)\n",
    "        for layer in range(2,n):\n",
    "            for i in range(n):\n",
    "                j = i + layer\n",
    "                if j < n:\n",
    "                    if s[i] == s[j] and dp1[i+1][j-1]:\n",
    "                        dp1[i][j] = True \n",
    "                        hashmap[j].append(i)\n",
    "        dp2 = [1]\n",
    "        for i in range(1,n):\n",
    "            l = hashmap[i]\n",
    "            x = n\n",
    "            for j in l:\n",
    "                if j == 0:\n",
    "                    x = 1\n",
    "                    break\n",
    "                else:\n",
    "                    x = min(x,dp2[j-1] + 1)\n",
    "            dp2.append(x)\n",
    "        return dp2[-1] - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # 预处理以每个字符为中心的回文串\n",
    "        p = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            p[i][i] = True\n",
    "            if i < n - 1 and s[i] == s[i + 1] and i + 1 < n:\n",
    "                p[i][i + 1] = True\n",
    "        for k in range(3, n + 1):\n",
    "            for i in range(n - k + 1):\n",
    "                j = i + k - 1\n",
    "                if s[i] == s[j] and p[i + 1][j - 1]:\n",
    "                    p[i][j] = True\n",
    "        # 构建图并计算拓扑序\n",
    "        graph = [[] for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if p[i][j]:\n",
    "                    graph[i].append(j + 1)\n",
    "        in_degree = [0] * (n + 2)\n",
    "        for i in range(n + 1):\n",
    "            for j in graph[i]:\n",
    "                in_degree[j] += 1\n",
    "        queue = [i for i in range(n + 1) if in_degree[i] == 0]\n",
    "        topo_order = []\n",
    "        while queue:\n",
    "            curr = queue.pop(0)\n",
    "            topo_order.append(curr)\n",
    "            for neighbor in graph[curr]:\n",
    "                in_degree[neighbor] -= 1\n",
    "                if in_degree[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "        # 计算从起始位置到每个位置的最小分割数\n",
    "        cut = [float('inf')] * (n + 1)\n",
    "        cut[0] = -1\n",
    "        for i in topo_order:\n",
    "            for j in graph[i]:\n",
    "                cut[j] = min(cut[j], cut[i] + 1)\n",
    "        return cut[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "            找最浅的树枝，start\n",
    "            用回溯会超时，24/36\n",
    "            使用动态规划来做\n",
    "            minCut[i]表示到s[i]为末尾（闭区间）的最少分割次数\n",
    "            minCut[i] = min(minCut[j]) +1, 其中s[j+1:i]为回文串 -> for枚举\n",
    "            -> 为快速判断某子串是否为回文串，先利用判断回文串的动态规划预处理一遍s\n",
    "            dp[i][j] = dp[i+1][j-1] and s[i] == s[j]\n",
    "        \"\"\"\n",
    "        self.length = len(s)\n",
    "        self.result = self.length\n",
    "        dp = np.identity(self.length) # 单位矩阵\n",
    "        # dp = np.ones((self.length, self.length)) # 如何确定动规初始值\n",
    "        for i in range(self.length-1, -1, -1): # 倒序\n",
    "            for j in range(i+1, self.length):\n",
    "                if i+1 < j-1:\n",
    "                    dp[i][j] = dp[i+1][j-1] == 1 and s[i] == s[j]\n",
    "                else:\n",
    "                    dp[i][j] = s[i] == s[j]\n",
    "                    continue\n",
    "        print(dp)\n",
    "\n",
    "        mincut = [self.length-1] * self.length\n",
    "        for i in range(self.length):\n",
    "            if dp[0][i] == 1: # 本身就是回文，不用分割\n",
    "                mincut[i] = 0\n",
    "            else:\n",
    "                for j in range(0, i): # 枚举\n",
    "                    if dp[j+1][i] == 1:\n",
    "                        mincut[i] = min(mincut[i], mincut[j]+1)\n",
    "        return mincut[-1]\n",
    "\n",
    "\n",
    "    def isHuiwen(self, s: str, left: int, right: int) -> bool:\n",
    "        # 双指针判断s[left:right]（左闭右开）是否是一个回文串\n",
    "        if len(set(s[left:right])) == 1:\n",
    "            return True\n",
    "        while(left < right):\n",
    "            right -= 1\n",
    "            if s[left] != s[right]:\n",
    "                return False\n",
    "            left += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def solve(self, cur, n, m, memo):\n",
    "        if cur == n:\n",
    "            return 0\n",
    "\n",
    "        if cur in memo:\n",
    "            return memo[cur]\n",
    "\n",
    "        min_val = 0x7fffffff\n",
    "        for end in m[cur]:\n",
    "            min_val = min(min_val, self.solve(end + 1, n, m, memo))\n",
    "        memo[cur] = min_val + 1\n",
    "        return min_val + 1\n",
    "\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[False for _ in range(n)] for _ in range(n)]\n",
    "        m = {i:[i] for i in range(n)}      # 回文起点到终点的记录\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i][i] = True\n",
    "            for j in range(i+1, n):\n",
    "                if j == i + 1:\n",
    "                    dp[i][j] =  s[i] == s[j]\n",
    "                else:\n",
    "                    dp[i][j] = s[i] == s[j] and dp[i+1][j-1]\n",
    "                if dp[i][j]:\n",
    "                    m[i].append(j)\n",
    "\n",
    "        return self.solve(0, n, m, {}) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[True] * n for _ in range(n)]\n",
    "        g = [[9999] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            g[i][i] = 0\n",
    "            for j in range(i + 1, n):\n",
    "                f[i][j] = (s[i] == s[j]) and f[i + 1][j - 1]\n",
    "                if f[i][j]:\n",
    "                    g[i][j] = 0\n",
    "\n",
    "        def dfs(l, r):\n",
    "            if g[l][r] < 9999:\n",
    "                return g[l][r]\n",
    "            m = 9999\n",
    "            for i in range(l, r):\n",
    "                if f[l][i]:\n",
    "                    m = min(m, dfs(i + 1, r) + 1)\n",
    "            g[l][r] = m\n",
    "            return m\n",
    "        \n",
    "        return dfs(0, n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        g = [[True] * n for _ in range(n)]\n",
    "        print(g)\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                g[i][j] = (s[i] == s[j]) and g[i + 1][j - 1]\n",
    "\n",
    "        f = [float(\"inf\")] * n\n",
    "        for i in range(n):\n",
    "            if g[0][i]:\n",
    "                f[i] = 0\n",
    "            else:\n",
    "                for j in range(i):\n",
    "                    if g[j + 1][i]:\n",
    "                        f[i] = min(f[i], f[j] + 1)\n",
    "\n",
    "        return f[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        if l == 1: return 0\n",
    "\n",
    "        dp = [[0] *l for i in range(l)]\n",
    "        for i in range(l):\n",
    "            dp[i][i] = 1\n",
    "        subs_i = [[] for i in range(l)]\n",
    "        subs_j = [[] for i in range(l)]\n",
    "        #print(dp)\n",
    "        for i in range(l-1,-1,-1):\n",
    "            for j in range(i,l):\n",
    "                if s[i] == s[j]:\n",
    "                    if j-i<=2:\n",
    "                        dp[i][j] = 1\n",
    "                     #   print(i,j,dp[i][j])\n",
    "                        subs_i[i].append(j)\n",
    "                        subs_j[j].append(i)\n",
    "                    elif dp[i+1][j-1]==1:\n",
    "                        dp[i][j] =1\n",
    "                        subs_i[i].append(j)\n",
    "                        subs_j[j].append(i)\n",
    "                       # print(i,j,dp[i][j])\n",
    "        # subs_i 里面存储的是每一个起始点为i的回文子串的终止点\n",
    "        # subs_j 里面存储的是每一个终止点为j的回文子串的起始点\n",
    "        # dp[i] 代表到i为止的最短的分割次数\n",
    "        dp = [-1 for i in range(l)]\n",
    "        # 初始化：所有从0开始的子串和0一样最少分割0次\n",
    "        for j in subs_i[0]:\n",
    "            dp[j] = 0\n",
    "        for j in range(1,l):\n",
    "            if dp[j] == -1:\n",
    "                #以j为终止又多少次分割次数：等于所有以i开始j结束的子串的前一位置i-1的最小分割次数+1\n",
    "                min_cut = 10000\n",
    "                for i in subs_j[j]:\n",
    "                    if i-1>=0:\n",
    "                        min_cut = min(dp[i-1],min_cut)\n",
    "                dp[j] = min_cut +1\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        dp = [[False]*len(s) for _ in range(len(s))]\n",
    "        res = 0\n",
    "        left = 0\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            for j in range(len(s)-1, i-1, -1):\n",
    "                if i == j:\n",
    "                    dp[i][j] = True\n",
    "                else:\n",
    "                    if s[i] == s[j]:\n",
    "                        if i+1 == j or dp[i+1][j-1]:\n",
    "                            dp[i][j] = True\n",
    "        maxCount = 0\n",
    "        memory = [-1] * len(s)\n",
    "        memory.append(0)#超出部分分割次数为0\n",
    "        def traversal(dp, i):\n",
    "            # if i == len(dp):\n",
    "            #     return 0\n",
    "            res = float('inf')\n",
    "            for ii,f in enumerate(dp[i][i:]):\n",
    "                if f == True:\n",
    "                    res = min(res, traversal(dp, ii+1+i) if memory[ii+1+i] == -1 else memory[ii+1+i])\n",
    "            count = min(res, float('inf'))+1\n",
    "            memory[i] = count\n",
    "            return count\n",
    "        return traversal(dp, 0)-1\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        dp = [[False]*len(s) for _ in range(len(s))]\n",
    "        res = 0\n",
    "        left = 0\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            for j in range(len(s)-1, i-1, -1):\n",
    "                if i == j:\n",
    "                    dp[i][j] = True\n",
    "                else:\n",
    "                    if s[i] == s[j]:\n",
    "                        if i+1 == j or dp[i+1][j-1]:\n",
    "                            dp[i][j] = True\n",
    "        dp1 = list(range(len(s)))\n",
    "        for i in range(len(s)):\n",
    "            if dp[0][i]:\n",
    "                dp1[i] = 0\n",
    "                continue\n",
    "            for j in range(i):\n",
    "                if dp[j+1][i]:\n",
    "                    dp1[i] = min(dp1[j]+1, dp1[i])\n",
    "        return dp1[-1]\n",
    "                    \n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        dp = [[False]*len(s) for _ in range(len(s))]\n",
    "        res = 0\n",
    "        left = 0\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            for j in range(len(s)-1, i-1, -1):\n",
    "                if i == j:\n",
    "                    dp[i][j] = True\n",
    "                else:\n",
    "                    if s[i] == s[j]:\n",
    "                        if i+1 == j or dp[i+1][j-1]:\n",
    "                            dp[i][j] = True\n",
    "        maxCount = 0\n",
    "        memory = [-1] * len(s)\n",
    "        memory.append(0)#超出部分分割次数为0\n",
    "        def traversal(dp, i):\n",
    "            # if i == len(dp):\n",
    "            #     return 0\n",
    "            res = float('inf')\n",
    "            for ii,f in enumerate(dp[i][i:]):\n",
    "                if f == True:\n",
    "                    res = min(res, traversal(dp, ii+1+i) if memory[ii+1+i] == -1 else memory[ii+1+i])\n",
    "            count = res+1\n",
    "            memory[i] = count\n",
    "            return count\n",
    "        return traversal(dp, 0)-1            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 220 ms ... 99 % ... 60.3 MB ... 9 %\n",
    "        #  time: O(n^2)\n",
    "        # space: O(n^2)\n",
    "        \n",
    "        n = len(s)\n",
    "        matching = collections.defaultdict(set)    # matching[i] = {j1,j2,...} 表示 s[j:i+1] 是回文子串\n",
    "        for c in range(n):\n",
    "            j, i = c-1, c+1\n",
    "            while j >= 0 and i < n and s[j] == s[i]:\n",
    "                matching[i].add(j)\n",
    "                j -= 1\n",
    "                i += 1\n",
    "        for i in range(n):\n",
    "            j = i-1\n",
    "            while j >= 0 and i < n and s[j] == s[i]:\n",
    "                matching[i].add(j)\n",
    "                j -= 1\n",
    "                i += 1\n",
    "        dp = [0] * n                               # dp[i] 表示让 s[:i+1] 回文化所需的最少切割次数\n",
    "        for i in range(n):\n",
    "            if i:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            for j in matching[i]:\n",
    "                if j:\n",
    "                    dp[i] = min(dp[i], dp[j-1] + 1)\n",
    "                else:\n",
    "                    dp[i] = 0\n",
    "        return dp[-1]\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 类似题目 2472. 不重叠回文子字符串的最大数目 https://leetcode.cn/problems/maximum-number-of-non-overlapping-palindrome-substrings/\n",
    "    # 139. 单词拆分 https://leetcode.cn/problems/word-break/\n",
    "    def minCut(self, s: str) -> int:\n",
    "        # 判断回文子串 + 类似最长递增子序列 求出 最少分割次数\n",
    "        n = len(s)\n",
    "        g = [[True] * n for _ in range(n)] #g[i][j]表示s[i..j]是否是回文串\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                g[i][j] = (s[i] == s[j]) and g[i + 1][j - 1]\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if g[i][n - 1]: return 0\n",
    "            res = inf\n",
    "            for j in range(i, n): # j的枚举顺序无所谓\n",
    "                if g[i][j]:\n",
    "                    res = min(res, 1 + dfs(j + 1))\n",
    "            return res\n",
    "        # return dfs(0)\n",
    "\n",
    "\n",
    "        # 任何字符串都至多经过n-1次分割，即分割成长度均为1的字符串，每个都是回文，因此必定有解\n",
    "        f = [inf] * n # 设 f[i] 表示字符串的前缀 s[0..i] （选择s[0..i]范围内全部元素）的最少分割次数\n",
    "        f[0] = 0\n",
    "        for i in range(1, n):\n",
    "            if g[0][i]: # 特判s[0..i]是回文串的情况，分割次数为0\n",
    "                f[i] = 0\n",
    "                continue\n",
    "            # [0..i] 范围内最后一个回文串[j+1..i]\n",
    "            for j in range(i):  \n",
    "                if g[j+1][i]:\n",
    "                    f[i]= min(f[i], f[j] + 1) # [0..i] = [0..j] + 1 (1为分割[j+1..i])\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    history={}\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        vaild=np.ones((n,n),dtype=int)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                vaild[i][j]=int(s[i]==s[j] and vaild[i+1][j-1])\n",
    "\n",
    "        dp=np.ones(n,dtype=int)*n\n",
    "        dp[0]=0\n",
    "        for i in range(n):\n",
    "            if vaild[0][i]==1:\n",
    "                dp[i]=0\n",
    "                continue\n",
    "\n",
    "            for j in range(i):\n",
    "                extra_cost=1 if vaild[j+1][i] else i-j+1\n",
    "                dp[i]=min(dp[j]+extra_cost,dp[i])\n",
    "        return int(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "import sys\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        dp = [sys.maxsize for _ in range(len(s))]\n",
    "        is_palindrome = np.zeros((len(s),len(s)),dtype=int).tolist()\n",
    "        for i in range(len(s)):\n",
    "            is_palindrome[i][i] = 1\n",
    "\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            for j in range(i,len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    if j-i<=2:\n",
    "                        is_palindrome[i][j] = 1\n",
    "                    elif is_palindrome[i+1][j-1] == 1:\n",
    "                        is_palindrome[i][j] = 1\n",
    "                else:\n",
    "                    is_palindrome[i][j] = 0\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            if is_palindrome[0][i] == 1:\n",
    "                dp[i] = 0\n",
    "                continue\n",
    "            for j in range(i):\n",
    "                if is_palindrome[j+1][i] == 1:\n",
    "                    dp[i] = min(dp[i], dp[j] + 1)\n",
    "        return dp[len(s)-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        dp = [[False] * l for _ in range(l)]\n",
    "        pre = [[i] for i in range(l)]\n",
    "        for i in range(l-1):\n",
    "            dp[i][i] = True\n",
    "            if s[i] == s[i+1]:\n",
    "                dp[i][i+1] = True\n",
    "                pre[i+1].append(i)\n",
    "        dp[l-1][l-1] = True\n",
    "\n",
    "\n",
    "        for i in range(l-3,-1,-1):\n",
    "            for j in range(i+2,l):\n",
    "                if s[i]==s[j] and dp[i+1][j-1]:\n",
    "                    dp[i][j] = True\n",
    "                    pre[j].append(i)\n",
    "        \n",
    "        # print(dp)\n",
    "\n",
    "        dp2 = [i for i in range(l)]\n",
    "\n",
    "        for i in range(1,l):\n",
    "            for index in pre[i]:\n",
    "                if index == 0:\n",
    "                    dp2[i] = 0\n",
    "                else:\n",
    "                    dp2[i] = min(dp2[i],dp2[index-1]+1) \n",
    "\n",
    "        return dp2[l-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        f = [[False] * (n + 1) for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i][i] = True\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = f[i+1][j-1] or (i + 1 == j)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n - 1:\n",
    "                return 0\n",
    "\n",
    "            if f[i][n-1]:\n",
    "                return 0\n",
    "\n",
    "            res = n - i - 1\n",
    "            for j in range(i + 1, n):\n",
    "                if f[i][j - 1]:\n",
    "                    res = min(res, dfs(j) + 1)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> List[List[str]]:\n",
    "        #202042120135杨桃\n",
    "        d=defaultdict(set)\n",
    "        N=len(s)\n",
    "        #用来找回文串，在某个位置开始延展如果是回文串就把它延展的宽度的位置记下来\n",
    "        def helper(i,j):\n",
    "            while i>=0 and j<N and s[i]==s[j]:\n",
    "                d[i].add(j)\n",
    "                i-=1\n",
    "                j+=1\n",
    "        #然后每个位点都试一次\n",
    "        for k in range(N):\n",
    "            helper(k,k)#偶数\n",
    "            helper(k,k+1)#奇数\n",
    "        @lru_cache(None)\n",
    "        def dfs(i):\n",
    "            #边界位\n",
    "            if i==N: return 0\n",
    "            #套loop加递归\n",
    "            tmp=[]\n",
    "            for j in range(i,N+1):#i位开始到N+1\n",
    "                if j in d[i]:\n",
    "                    tmp.append(dfs(j+1)+1)\n",
    "            return min(tmp) #返回的必须是个数才可以append\n",
    "        \n",
    "        return dfs(0)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        path = []\n",
    "\n",
    "        # isParlindrom 预处理\n",
    "        self.isPalindrome = [[True] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                self.isPalindrome[i][j] = (s[i] == s[j]) and self.isPalindrome[i + 1][j - 1]\n",
    "\n",
    "        return self.dfs(s, 0)\n",
    "    \n",
    "    @cache\n",
    "    def dfs(self, s, start):\n",
    "        n = len(s)\n",
    "        ans = n - 1\n",
    "\n",
    "        if start >= n - 1:\n",
    "            return 0\n",
    "        for i in range(start, n):\n",
    "            if self.isPalindrome[start][i]:\n",
    "                if i == n - 1:\n",
    "                    ans = min(ans, self.dfs(s, i + 1))\n",
    "                else:\n",
    "                    ans = min(ans, self.dfs(s, i + 1) + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        table = defaultdict(list)\n",
    "        dp = [[False for i in range(n)] for j in range(n)]\n",
    "        for dist in range(n):\n",
    "            for i in range(n - dist):\n",
    "                j = i + dist\n",
    "                if s[i] == s[j] and (i + 1 > j - 1 or dp[i+1][j-1]):\n",
    "                    dp[i][j] = True\n",
    "                    table[j].append(i)\n",
    "                    \n",
    "        #print(dp)\n",
    "        memo = {}\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            nonlocal memo\n",
    "            res = inf\n",
    "            if i in memo:\n",
    "                return memo[i]\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            for j in table[i]:\n",
    "                res = min(res, 1 + dfs(j - 1))\n",
    "            memo[i] = res\n",
    "            return memo[i]\n",
    "        return dfs(n-1) - 1\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        res=defaultdict(list)\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1,len(s)+1):\n",
    "                if s[i:j]==s[i:j][::-1]:#如果i到j-1是回文，可以从i调到j\n",
    "                    res[i].append(j)\n",
    "        #bfs\n",
    "        visted=set()\n",
    "        q=Queue()\n",
    "        q.put((0,0))\n",
    "        while not q.empty():\n",
    "            end,step=q.get()\n",
    "            if end==len(s): #到达了\n",
    "                break\n",
    "            if end in visted:\n",
    "                continue\n",
    "            visted.add(end)\n",
    "            for i in res[end]:\n",
    "                q.put((i,step+1))\n",
    "        return step-1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        isreverse = [[-1 for _ in range(n)] for __ in range(n)]\n",
    "        \n",
    "        def g(i, j):\n",
    "            if isreverse[i][j] != -1:\n",
    "                return isreverse[i][j]\n",
    "            if i == j:\n",
    "                return True\n",
    "            if i == j-1 and s[i] == s[j]:\n",
    "                return True\n",
    "            isreverse[i][j] = s[i] == s[j] and g(i+1, j-1)\n",
    "            return isreverse[i][j]\n",
    "\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i >= len(s):\n",
    "                return 0\n",
    "            a = [f(j+1)+1 for j in range(i, len(s)) if g(i, j) == True]\n",
    "            return min(a) if a else 0\n",
    "\n",
    "        return f(0)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        b = [[0] * (length + 1) for _ in range(length + 1)]\n",
    "        for i in range(1, length + 1):\n",
    "            for j in range(i, 0, -1):\n",
    "                if i == j:\n",
    "                    b[j][i] = 1\n",
    "                elif i - j == 1 and s[i-1] == s[j-1]:\n",
    "                    b[j][i] = 1\n",
    "                elif b[j+1][i-1] and s[i-1] == s[j-1]:\n",
    "                    b[j][i] = 1\n",
    "        \n",
    "        dp = [0] * (length + 1)\n",
    "        for i in range(1, length+1):\n",
    "            if b[1][i]:\n",
    "                dp[i] == 0\n",
    "            else:\n",
    "                dp[i] = i - 1\n",
    "                for j in range(i, 0, -1):\n",
    "                    if b[j][i]:\n",
    "                        dp[i] = min(dp[i], dp[j-1] + 1)\n",
    "        print(b)\n",
    "        print(dp)\n",
    "        return dp[length]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        #\n",
    "        n = len(s)\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        # dp[i][j] s[i:j + 1] is palindrome\n",
    "        for i in range(n):\n",
    "            dp[i][i] = True\n",
    "        for i in range(n - 1):\n",
    "            if s[i] == s[i + 1]:\n",
    "                dp[i][i + 1] = True\n",
    "        for l in range(2, n):\n",
    "            for i in range(n - l):\n",
    "                if s[i] == s[i + l] and dp[i + 1][i + l - 1]:\n",
    "                    dp[i][i + l] = True\n",
    "        \n",
    "        @cache\n",
    "        def dfs(left, right):\n",
    "            if dp[left][right]:\n",
    "                return 0\n",
    "            cur = n \n",
    "            for i in range(left, right):\n",
    "                if dp[left][i]:\n",
    "                    cur = min(cur, dfs(i + 1, right) + 1)\n",
    "            return cur\n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        N = len(s)\n",
    "        dp = [[None]*N for _ in range(N)]\n",
    "        memo = [[None]*N for _ in range(N)]\n",
    "        for n in range(N):\n",
    "            dp[n][n] = True\n",
    "            memo[n][n] = 0\n",
    "        for n in range(N-1):\n",
    "            dp[n][n+1] = True if s[n] == s[n+1] else False\n",
    "            memo[n][n+1] = 0 if dp[n][n+1] else None\n",
    "        for i in range(N-3, -1, -1):\n",
    "            for j in range(i+2, N):\n",
    "                dp[i][j] = True if s[i] == s[j] and dp[i+1][j-1] else False\n",
    "                memo[i][j] = 0 if dp[i][j] else None\n",
    "        def Rec(s, L, R=len(s), memo=memo):\n",
    "            if dp[L][R-1]: return 0\n",
    "            if memo[L][R-1] == None:\n",
    "                vmin = len(s) + 1\n",
    "                for i in range(L, R):\n",
    "                    if dp[L][i]:\n",
    "                        vmin = min(vmin, 1+Rec(s, i+1))\n",
    "                memo[L][R-1] = vmin\n",
    "            return memo[L][R-1]\n",
    "        return Rec(s, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    memo = []\n",
    "    def minCut(self, s: str) -> int:\n",
    "        self.memo = [[0 for i in range(len(s))] for jj in range(len(s))]\n",
    "        print(self.memo)\n",
    "\n",
    "        f = self.prepare(s)\n",
    "        return self.dfs(s, f)\n",
    "\n",
    "    #dp[i] 0-i包括的分割次数\n",
    "    #      j          i\n",
    "    #      * f[j][i]  *\n",
    "    #   dp[j]        dp[i]\n",
    "    def dfs(self, s, f):\n",
    "        n = len(s)\n",
    "\n",
    "        dp = [n] * (n)\n",
    "\n",
    "        for i in range(n):\n",
    "            #print(i, f[0][i])\n",
    "            #1 dp方法\n",
    "            #if f[0][i]:\n",
    "            #2 递归方法\n",
    "\n",
    "            #print(\"short\", i, s, s[0:i+1],  self.isP(s, 0, i))\n",
    "            if self.isP(s, 0, i) == 1:\n",
    "                dp[i] = 0\n",
    "            else:\n",
    "                for j in range(0, i):\n",
    "                    #2 递归方法\n",
    "                    #print(i,j, s, s[j+1:i+1], dp[j], self.isP(s, j+1, i))\n",
    "                    #if self.isP(s, j+1, i) == 1:\n",
    "                    #1 \n",
    "                    #print(f[j+1][i], j+1, i)\n",
    "                    if f[j+1][i]:\n",
    "                        dp[i] = min(dp[i], dp[j] + 1)\n",
    "        #print(dp)\n",
    "        return dp[n-1]\n",
    "\n",
    "    def prepare(self, s):\n",
    "        n = len(s)\n",
    "        f = [[True for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j] and f[i+1][j-1]:\n",
    "                    f[i][j] = True\n",
    "                else:\n",
    "                    f[i][j] = False\n",
    "        #print(f)\n",
    "        return f\n",
    "\n",
    "    def isP(self, s, i, j):\n",
    "        #增加记忆\n",
    "        if self.memo[i][j]:\n",
    "            return self.memo[i][j]\n",
    "\n",
    "        if i < 0 or j >= len(s):\n",
    "            self.memo[i][j] = -1\n",
    "            return -1\n",
    "\n",
    "        if i == j:\n",
    "            self.memo[i][j] = 1\n",
    "            return 1\n",
    "\n",
    "        if i > j:\n",
    "            self.memo[i][j] = 1\n",
    "            return 1\n",
    "        \n",
    "        if s[i] != s[j]:\n",
    "            self.memo[i][j] = -1\n",
    "            return -1\n",
    "        else:\n",
    "            return self.isP(s, i + 1, j - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    memo = []\n",
    "    def minCut(self, s: str) -> int:\n",
    "        self.memo = [[0 for i in range(len(s))] for jj in range(len(s))]\n",
    "        print(self.memo)\n",
    "\n",
    "        f = self.prepare(s)\n",
    "        return self.dfs(s, f)\n",
    "\n",
    "    #dp[i] 0-i包括的分割次数\n",
    "    #      j          i\n",
    "    #      * f[j][i]  *\n",
    "    #   dp[j]        dp[i]\n",
    "    def dfs(self, s, f):\n",
    "        n = len(s)\n",
    "\n",
    "        dp = [n] * (n)\n",
    "\n",
    "        for i in range(n):\n",
    "            #print(i, f[0][i])\n",
    "            #1 dp方法\n",
    "            #if f[0][i]:\n",
    "            #2 递归方法\n",
    "\n",
    "            #print(\"short\", i, s, s[0:i+1],  self.isP(s, 0, i))\n",
    "            if self.isP(s, 0, i) == 1:\n",
    "                dp[i] = 0\n",
    "            else:\n",
    "                for j in range(0, i):\n",
    "                    #2 递归方法\n",
    "                    #print(i,j, s, s[j+1:i+1], dp[j], self.isP(s, j+1, i))\n",
    "                    #if self.isP(s, j+1, i) == 1:\n",
    "                    #1 \n",
    "                    if f[j+1][i]:\n",
    "                        dp[i] = min(dp[i], dp[j] + 1)\n",
    "        #print(dp)\n",
    "        return dp[n-1]\n",
    "\n",
    "    def prepare(self, s):\n",
    "        n = len(s)\n",
    "        f = [[True for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j] and f[i+1][j-1]:\n",
    "                    f[i][j] = True\n",
    "                else:\n",
    "                    f[i][j] = False\n",
    "        #print(f)\n",
    "        return f\n",
    "\n",
    "    def isP(self, s, i, j):\n",
    "        #增加记忆\n",
    "        if self.memo[i][j]:\n",
    "            return self.memo[i][j]\n",
    "\n",
    "        if i < 0 or j >= len(s):\n",
    "            self.memo[i][j] = -1\n",
    "            return -1\n",
    "\n",
    "        if i == j:\n",
    "            self.memo[i][j] = 1\n",
    "            return 1\n",
    "\n",
    "        if i > j:\n",
    "            self.memo[i][j] = 1\n",
    "            return 1\n",
    "        \n",
    "        if s[i] != s[j]:\n",
    "            self.memo[i][j] = -1\n",
    "            return -1\n",
    "        else:\n",
    "            return self.isP(s, i + 1, j - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        dic={}\n",
    "        for i in range(len(s)):\n",
    "            dic[i]={i+1}\n",
    "        dp=[[False]*len(s) for i in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i,-1,-1):\n",
    "                if i==j:\n",
    "                    dp[j][i]=True\n",
    "                elif i-j==1:\n",
    "                    if s[i]==s[j]:\n",
    "                        dp[j][i]=True\n",
    "                        dic[j].add(i+1)\n",
    "                else:\n",
    "                    if dp[j+1][i-1] and s[i]==s[j]:\n",
    "                        dp[j][i]=True\n",
    "                        dic[j].add(i+1)\n",
    "        cnt=0\n",
    "        cur={0}\n",
    "        while len(s) not in cur:\n",
    "            nextSet=set()\n",
    "            for i in cur:\n",
    "                nextSet|=dic[i]\n",
    "            cur=nextSet\n",
    "            cnt+=1\n",
    "        return cnt-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        # 动态规划\n",
    "        palindrome = set([(i,i+1) for i in range(len(s))] + [(i,i+2) for i in range(len(s)-1) if s[i]==s[i+1]])  # 长度为1和2的回文子串的下标\n",
    "        min_cut = [0]  # 动态数组，存放到第1，2，3，。。。，len(s)个字符为止的子串的最小分割次数\n",
    "        for i in range(1,len(s)):\n",
    "            i_cut = len(s)\n",
    "            for j in range(0,i+1):\n",
    "                if i + 1 - j > 2:\n",
    "                    if s[j] == s[i] and (j+1, i) in palindrome:\n",
    "                        palindrome.add((j,i+1))\n",
    "                if (j,i+1) in palindrome:\n",
    "                    if j > 0:\n",
    "                        i_cut = min(i_cut,min_cut[j-1] + 1)\n",
    "                    else:\n",
    "                        i_cut = 0\n",
    "                        break\n",
    "            min_cut.append(i_cut)\n",
    "        return min_cut[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        N = len(s)\n",
    "        dp = [1]*(N+1)\n",
    "        cdds = [[0,1] for i in range(N)]\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(1,N):\n",
    "            c = s[i]\n",
    "            dp[i+1]=dp[i]+1\n",
    "            for l in cdds[i-1]:\n",
    "                if i-1-l>=0 and s[i-1-l]==c:\n",
    "                    dp[i+1] = min(dp[i+1],dp[i-1-l]+1)\n",
    "                    cdds[i].append(l+2)\n",
    "        \n",
    "        return dp[-1]-1\n",
    "\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.palindromeCache = None\n",
    "        self.minCutCache = None\n",
    "\n",
    "    def minCut(self, s: str) -> int:\n",
    "        self.palindromeCache = [[False for i in range(len(s) + 1)] for j in range(len(s))]\n",
    "        self.minCutCache = [[None for i in range(len(s) + 1)] for j in range(len(s))]\n",
    "\n",
    "        self.buildCaches(s)\n",
    "\n",
    "        return self.inner_minCut(s, 0, len(s))\n",
    "\n",
    "    def buildCaches(self, s:str) -> None:\n",
    "        for j in range(1, len(s) + 1):\n",
    "            for i in range(len(s) - j + 1):\n",
    "                if j == 1:\n",
    "                    self.palindromeCache[i][j] = True\n",
    "                else:\n",
    "                    self.palindromeCache[i][j] = (s[i] == s[i + j - 1]) if j == 2 else ((s[i] == s[i + j - 1]) and self.palindromeCache[i+1][j-2])\n",
    "\n",
    "                if self.palindromeCache[i][j] == True:\n",
    "                    self.minCutCache[i][j] = 0\n",
    "\n",
    "    def inner_minCut(self, s: str, start:int, length: int) -> int:\n",
    "\n",
    "        if length <= 1:\n",
    "            return 0\n",
    "        \n",
    "        if self.minCutCache[start][length] is not None:\n",
    "            return self.minCutCache[start][length]\n",
    "\n",
    "        l = length\n",
    "        cut = math.inf\n",
    "        while l >= 1:\n",
    "\n",
    "            if self.palindromeCache[start][l]:\n",
    "                if l < length:\n",
    "                    cut = min(cut, self.inner_minCut(s, start+l, length-l) + 1)\n",
    "                else:\n",
    "                    cut = 0\n",
    "\n",
    "            if cut == 0:\n",
    "                break\n",
    "\n",
    "            l -= 1\n",
    "\n",
    "        cut = cut if cut != math.inf else 0\n",
    "\n",
    "        self.minCutCache[start][length] = cut\n",
    "\n",
    "        return cut\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        revs = set()\n",
    "        l = len(s)\n",
    "        for i in range(l):\n",
    "            for j in range(i, -1, -1):\n",
    "                if j == i or (s[i] == s[j] and (j == i - 1 or (j + 1, i - 1) in revs)):\n",
    "                    revs.add((j, i))\n",
    "        ans = [0] * l\n",
    "        for i in range(l):\n",
    "            if (0, i) in revs:\n",
    "                ans[i] = 0\n",
    "            else:\n",
    "                ans[i] = i\n",
    "                for j in range(1, i + 1):\n",
    "                    if (j, i) in revs:\n",
    "                        ans[i] = min(ans[i], ans[j - 1] + 1)\n",
    "        return ans[l - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minCut(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        dp  = [[True] * n for i in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i][i] = True\n",
    "            for j in range(i+1, n):\n",
    "                dp[i][j] = dp[i+1][j-1] and (s[i] == s[j])\n",
    "        # for i in range(n):\n",
    "        #     print(dp[i])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i >=j:\n",
    "                return 0\n",
    "            if dp[i][j]:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for k in range(i, j):\n",
    "                if dp[k+1][j]:\n",
    "                    ans = min(ans, dfs(i, k) + 1)\n",
    "            return ans\n",
    "           \n",
    "        return dfs(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        L = len(s)\n",
    "        huiwen = set()\n",
    "        for i in range(L - 1, -1, -1):\n",
    "            for j in range(i + 1, L):\n",
    "                if (i + 1, j - 1) in huiwen or j - 1 <= i + 1:\n",
    "                    if s[i] == s[j]:\n",
    "                        huiwen.add((i, j))\n",
    "        d = [0]*L\n",
    "        for i in range(1, L):\n",
    "            if (0, i) in huiwen:\n",
    "                continue\n",
    "            d[i] = d[i - 1] + 1\n",
    "            for j in range(i):\n",
    "                if (j + 1, i) in huiwen:\n",
    "                    d[i] = min(d[i], d[j] + 1)\n",
    "        return d[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ispal = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            j, k = i, i\n",
    "            while j >= 0 and k < n and s[j] == s[k]:\n",
    "                ispal[j][k] = True\n",
    "                j -= 1\n",
    "                k += 1\n",
    "            if i+1 < n and s[i] == s[i+1]:\n",
    "                j, k = i, i+1\n",
    "                while j >= 0 and k < n and s[j] == s[k]:\n",
    "                    ispal[j][k] = True\n",
    "                    j -= 1\n",
    "                    k += 1\n",
    "        \n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = n - i\n",
    "            for j in range(i, n):\n",
    "                if ispal[i][j]:\n",
    "                    res = min(res, f(j+1) + 1)\n",
    "            return res\n",
    "        return f(0) - 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        if len(s) == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            ifRever = np.zeros([len(s), len(s)])\n",
    "            for i in range(0, len(s)):\n",
    "                for j in range(i, len(s)):\n",
    "                    if ifRever[i, j] == 1 or ifRever[i, j] == -1:\n",
    "                        continue\n",
    "                    else:\n",
    "                        unsetII = []\n",
    "                        unsetJJ = []\n",
    "                        jj = j\n",
    "                        ii = i\n",
    "                        while jj >= ii:\n",
    "                            if s[ii] == s[jj]:\n",
    "                                unsetII.append(ii)\n",
    "                                unsetJJ.append(jj)\n",
    "                            else:\n",
    "                                ifRever[ii, jj] = -1\n",
    "                                ifRever[jj, ii] = -1\n",
    "                                for _ii, _jj in zip(unsetII, unsetJJ):\n",
    "                                    ifRever[_ii, _jj] = -1\n",
    "                                    ifRever[_jj, _ii] = -1\n",
    "                                unsetII = []\n",
    "                                unsetJJ = []\n",
    "                            jj -= 1\n",
    "                            ii += 1\n",
    "                        for _ii, _jj in zip(unsetII, unsetJJ):\n",
    "                            ifRever[_ii, _jj] = 1\n",
    "                            ifRever[_jj, _ii] = 1\n",
    "            AllComposeMap = {}\n",
    "            AllComposeMap[0] = [s[0]]\n",
    "            for i in range(1, len(s)):\n",
    "                if ifRever[0, i] == 1:\n",
    "                    AllComposeMap[i] = [s[:i + 1]]\n",
    "                    continue\n",
    "                else:\n",
    "                    for j in range(0, i):\n",
    "                        if ifRever[j + 1, i] == 1:\n",
    "                            if i not in AllComposeMap.keys():\n",
    "                                AllComposeMap[i] = AllComposeMap[j] + [s[j + 1:i + 1]]\n",
    "                            else:\n",
    "                                if len(AllComposeMap[j]) + 1 < len(AllComposeMap[i]):\n",
    "                                    AllComposeMap[i] = AllComposeMap[j] + [s[j + 1:i + 1]]\n",
    "            print(AllComposeMap)\n",
    "            return len(AllComposeMap[len(s) - 1]) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "\n",
    "        s = list(s)\n",
    "        len_ = len(s)\n",
    "        rec = {}\n",
    "        for i, v in enumerate(s):\n",
    "            l, r = i-1, i+1 \n",
    "            while l>=0 and r<= len_-1 and s[l] == s[r]:\n",
    "                if r not in rec:\n",
    "                    rec[r] = [(l, r)]\n",
    "                else:\n",
    "                    rec[r].append((l, r)) \n",
    "                l -=1\n",
    "                r +=1\n",
    "            # 双 \n",
    "            l, r = i, i+1\n",
    "            while l >=0 and r <=len_-1 and s[l]==s[r]:\n",
    "                if r not in rec:\n",
    "                    rec[r] = [(l, r)]\n",
    "                else:\n",
    "                    rec[r].append((l, r)) \n",
    "                l-=1\n",
    "                r+=1\n",
    "\n",
    "        dp = [None]*len(s)\n",
    "        for i, v in enumerate(s):\n",
    "            if i==0:\n",
    "                dp[i] = 0\n",
    "                continue\n",
    "            if i not in rec:\n",
    "                dp[i] = dp[i-1]+1\n",
    "            else:\n",
    "                m_ = dp[i-1]+1\n",
    "                for p in rec[i]:\n",
    "                    lft = 0 if p[0]==0 else dp[p[0]-1] +1\n",
    "                    m_ = min(m_, lft) \n",
    "                dp[i] = m_ \n",
    "\n",
    "        return dp[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        # 统计所有回文字符串\n",
    "        memo = []\n",
    "        for i in range(len(s)):\n",
    "            delta = 0\n",
    "            while i - delta >= 0 and i + delta < len(s) and s[i - delta] == s[i + delta]:\n",
    "                memo.append((i - delta, i + delta))\n",
    "                delta += 1\n",
    "            \n",
    "\n",
    "        for i in range(len(s) - 1):\n",
    "            delta = 0\n",
    "            while i - delta >= 0 and i + 1 + delta < len(s) and s[i - delta] == s[i + delta + 1]:\n",
    "                memo.append((i - delta, i + 1 + delta))\n",
    "                delta += 1\n",
    "        # print(memo)\n",
    "        data = {}\n",
    "        for i in memo:\n",
    "            if i[0] in data:\n",
    "                data[i[0]].append(i[1])\n",
    "            else:\n",
    "                data[i[0]] = [i[1]]\n",
    "        \n",
    "        queue = []\n",
    "        head = 0\n",
    "        visited = {}\n",
    "        for i in data[0]:\n",
    "            queue.append((i, 1))\n",
    "            visited[i] = 1\n",
    "        while head < len(queue):\n",
    "            index = queue[head][0]\n",
    "            cnt = queue[head][1]\n",
    "            if index == len(s) - 1:\n",
    "                return cnt - 1\n",
    "            for i in data[index + 1]:\n",
    "                if i not in visited or visited[i] > cnt:\n",
    "                    visited[i] = cnt\n",
    "                    queue.append((i, cnt + 1))\n",
    "            head += 1\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minCut(self, s: str) -> int:\n",
    "#         n = len(s)\n",
    "#         # f = [[0] * n for _ in range(n)]\n",
    "\n",
    "#         @cache\n",
    "#         def valid(i,j):\n",
    "#             if i>=j:\n",
    "#                 return True\n",
    "#             else:\n",
    "#                 return True if (s[i]==s[j] and valid(i+1,j-1)) else False\n",
    "        \n",
    "#         ans = 1999\n",
    "#         path = 0\n",
    "\n",
    "#         def dfs(i):\n",
    "#             nonlocal ans\n",
    "#             nonlocal path\n",
    "#             if i == n:\n",
    "#                 ans = min(ans,path)\n",
    "#                 return\n",
    "#             if path > ans:\n",
    "#                 return\n",
    "#             for j in range(i,n):\n",
    "#                 if valid(i,j):\n",
    "#                     path += 1\n",
    "#                     dfs(j+1)\n",
    "#                     path -= 1\n",
    "            \n",
    "#         dfs(0)\n",
    "\n",
    "#         return ans-1\n",
    "######################## 超时\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [n] * n\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "\n",
    "        # for i in range(0,n):\n",
    "        #     for j in range(0,i):\n",
    "        #         g[j][i] = s[i] == s[j] and g[j+1][i-1]\n",
    "        def valid(i,j):\n",
    "            if g[i][j] != 0:\n",
    "                return g[i][j]\n",
    "            if i>=j:\n",
    "                g[i][j] = 1\n",
    "            else:\n",
    "                g[i][j] = 1 if (s[i] == s[j] and valid(i+1,j-1)==1) else -1\n",
    "            return g[i][j]\n",
    "        # @cache\n",
    "        # def valid(i,j):\n",
    "        #     if i>=j:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         return True if (s[i]==s[j] and valid(i+1,j-1)) else False\n",
    "        \n",
    "        for i in range(0,n):\n",
    "            if valid(0,i)==1:\n",
    "            # if g[0][i]:\n",
    "                f[i] = 0\n",
    "            else:\n",
    "                for j in range(0,i):\n",
    "                    if valid(j+1,i)==1:\n",
    "                    # if g[j+1][i]:\n",
    "                        f[i] = min(f[i],f[j]+1)\n",
    "            \n",
    "        return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minCut(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        dp  = [[True] * n for i in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i][i] = True\n",
    "            for j in range(i+1, n):\n",
    "                dp[i][j] = dp[i+1][j-1] and (s[i] == s[j])\n",
    "        # for i in range(n):\n",
    "        #     print(dp[i])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if dp[0][i]:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for j in range(i):\n",
    "                if dp[j+1][i]:\n",
    "                    ans = min(ans, dfs(j) + 1)\n",
    "            return ans\n",
    "           \n",
    "        return dfs(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str):\n",
    "        cach = {}\n",
    "        if s is None or len(s) == 0:\n",
    "            return []\n",
    "        dp = [len(s)-1 for _ in range(len(s) + 1)]\n",
    "        for i in range(len(s)):\n",
    "            if self.isPalindrome(s[:i + 1], cach):\n",
    "                dp[i + 1] = 0\n",
    "                continue\n",
    "            for j in range(i, 0, -1):\n",
    "                if self.isPalindrome(s[j:i + 1], cach):\n",
    "                    dp[i + 1] = min(dp[i + 1], dp[j] + 1)\n",
    "                    if dp[i + 1] == 1:\n",
    "                        break\n",
    "\n",
    "        return dp[-1]\n",
    "\n",
    "    def isPalindrome(self, s: str, cach):\n",
    "        if len(s) <= 1:\n",
    "            return True\n",
    "        if s in cach:\n",
    "            return cach[s]\n",
    "        l = len(s)\n",
    "        for i in range(len(s)//2):\n",
    "            if s[i] != s[l-i-1]:\n",
    "                cach[s] = False\n",
    "                return False\n",
    "        cach[s] = True\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[True] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                dp[i][j] = dp[i+1][j-1] and s[i] == s[j]\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if dp[0][i]:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if dp[j+1][i]:\n",
    "                    res = min(res, dfs(j) + 1)\n",
    "            return res\n",
    "\n",
    "        return dfs(n-1)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
